import random

def generate_test_cases():
    """
    生成用于测试寻找数组中第K个最大元素算法的测试用例
    返回一个列表，每个元素是一个元组 (nums, k, description)
    """
    test_cases = []
    
    # 测试用例1：示例1 - 简单数组
    test_cases.append(([3, 2, 1, 5, 6, 4], 2, "示例1 - 简单数组"))
    
    # 测试用例2：示例2 - 包含重复元素的数组
    test_cases.append(([3, 2, 3, 1, 2, 4, 5, 5, 6], 4, "示例2 - 包含重复元素的数组"))
    
    # 测试用例3：单元素数组
    test_cases.append(([42], 1, "单元素数组"))
    
    # 测试用例4：两个元素数组 - 第1大
    test_cases.append(([10, 20], 1, "两个元素数组 - 第1大"))
    
    # 测试用例5：两个元素数组 - 第2大
    test_cases.append(([10, 20], 2, "两个元素数组 - 第2大"))
    
    # 测试用例6：全部相同元素的数组
    test_cases.append(([5, 5, 5, 5, 5], 3, "全部相同元素的数组"))
    
    # 测试用例7：有序数组 - 升序
    sorted_asc = list(range(1, 101))
    test_cases.append((sorted_asc, 50, "有序数组 - 升序"))
    
    # 测试用例8：有序数组 - 降序
    sorted_desc = list(range(100, 0, -1))
    test_cases.append((sorted_desc, 50, "有序数组 - 降序"))
    
    # 测试用例9：随机大数组 - 1000元素
    random_large = [random.randint(-10000, 10000) for _ in range(1000)]
    test_cases.append((random_large, 500, "随机大数组 - 1000元素"))
    
    # 测试用例10：随机大数组 - 10000元素
    random_very_large = [random.randint(-10000, 10000) for _ in range(10000)]
    test_cases.append((random_very_large, 5000, "随机大数组 - 10000元素"))
    
    # 测试用例11：极端情况 - 寻找最大元素
    random_arr = [random.randint(-10000, 10000) for _ in range(500)]
    test_cases.append((random_arr, 1, "极端情况 - 寻找最大元素"))
    
    # 测试用例12：极端情况 - 寻找最小元素
    random_arr2 = [random.randint(-10000, 10000) for _ in range(500)]
    test_cases.append((random_arr2, len(random_arr2), "极端情况 - 寻找最小元素"))
    
    return test_cases

if __name__ == "__main__":
    # 生成测试用例并打印
    test_cases = generate_test_cases()
    for i, (nums, k, desc) in enumerate(test_cases, 1):
        print(f"测试用例 {i} ({desc}):")
        if len(nums) <= 20:  # 只打印较短的数组
            print(f"  nums: {nums}")
        else:
            print(f"  nums: [{nums[0]}, {nums[1]}, ..., {nums[-2]}, {nums[-1]}] (长度: {len(nums)})")
        print(f"  k: {k}")
        print()